Introduction

• The Euclidean Algorithm is one of the oldest algorithms in mathematics.
• It provides a fast and reliable way to compute the greatest common divisor (GCD) of two integers.
• Despite its ancient origins, it remains essential in modern mathematics and computer science.

What Is the Greatest Common Divisor?

• The greatest common divisor of two integers $a$ and $b$ is:
  • the largest positive integer that divides both $a$ and $b$ without leaving a remainder.
• Examples:
  • $\gcd(12, 18) = 6$
  • $\gcd(20, 35) = 5$
  • $\gcd(7, 13) = 1$ (these are coprime)
• Key facts:
  • The GCD is always positive.
  • If one number divides the other, the GCD is the smaller number.
  • If two numbers share no common factors except $1$, their GCD is $1$.

Why Finding the GCD Matters

• The GCD appears in many areas:
  • Reducing fractions
  • Solving equations like $ax + by = c$
  • Cryptography, especially algorithms like RSA
  • Number theory, including modular arithmetic
  • Computer science, where efficient algorithms matter
• The Euclidean Algorithm is far faster than listing all divisors.

A First Look at the Euclidean Algorithm

• The algorithm is based on a simple idea:
  • Repeatedly replace a pair of numbers with a smaller pair that has the same GCD.
• Basic step:
  • If $a$ and $b$ are integers with $a > b$, divide $a$ by $b$: $$a = bq + r.$$
  • Then replace $(a, b)$ with $(b, r)$.
• Continue until the remainder becomes $0$.
• The last nonzero remainder is the GCD.

The Key Idea: Replacing Big Problems with Smaller Ones

• The crucial fact: $$\gcd(a, b) = \gcd(b, r).$$
• Why this helps:
  • $r$ is always smaller than $b$.
  • Each step shrinks the numbers.
  • The process must eventually reach $0$.
• This shrinking is what makes the algorithm fast.

Step‑by‑Step Examples

Example 1: $\gcd(252, 105)$

1. $252 = 105\cdot 2 + 42$
2. $105 = 42\cdot 2 + 21$
3. $42 = 21\cdot 2 + 0$

• Last nonzero remainder: 21
• So $\gcd(252, 105) = 21$.

Example 2: $\gcd(119, 34)$

1. $119 = 34\cdot 3 + 17$
2. $34 = 17\cdot 2 + 0$

• Last nonzero remainder: 17
• So $\gcd(119, 34) = 17$.

Example 3: $\gcd(48, 18)$

1. $48 = 18\cdot 2 + 12$
2. $18 = 12\cdot 1 + 6$
3. $12 = 6\cdot 2 + 0$

• Last nonzero remainder: 6
• So $\gcd(48, 18) = 6$.

Why the Euclidean Algorithm Always Works

• The algorithm works because:
  • Each step reduces the size of the numbers.
  • The GCD does not change when replacing $(a, b)$ with $(b, r)$.
  • Eventually the remainder becomes $0$.
• The last nonzero remainder must divide all previous remainders.
• Therefore, it is the greatest common divisor.

Extending the Algorithm to Negative Integers

• The GCD is always defined to be positive, even if inputs are negative.
• We can simply take absolute values: $$\gcd(a, b) = \gcd(|a|, |b|).$$
• The Euclidean Algorithm works the same way:
  • Replace $a$ with $|a|$ and $b$ with $|b|$.
  • Run the algorithm normally.

Common Mistakes and How to Avoid Them

• Mistake: Stopping too early.
  • The algorithm ends only when the remainder is 0.
• Mistake: Forgetting to carry the remainder forward.
  • Always replace $(a, b)$ with $(b, r)$.
• Mistake: Thinking the quotient matters.
  • Only the remainder is used in the next step.
• Mistake: Mixing up the order.
  • Always divide the larger number by the smaller one.

Calculator

Exercises

Try to compute each GCD using the Euclidean Algorithm.
Show the sequence of divisions when possible.

1. Compute $\gcd(84, 30)$.

   Solution

   $\gcd(84, 30)$

   • $84 = 30\cdot 2 + 24$
   • $30 = 24\cdot 1 + 6$
   • $24 = 6\cdot 4 + 0$
   • Last nonzero remainder: $6$
   • Answer: $\gcd(84, 30) = 6$.
2. Compute $\gcd(99, 78)$.

   Solution

   $\gcd(99, 78)$

   • $99 = 78\cdot 1 + 21$
   • $78 = 21\cdot 3 + 15$
   • $21 = 15\cdot 1 + 6$
   • $15 = 6\cdot 2 + 3$
   • $6 = 3\cdot 2 + 0$
   • Last nonzero remainder: $3$
   • Answer: $\gcd(99, 78) = 3$.
3. Compute $\gcd(56, 15)$.

   Solution

   $\gcd(56, 15)$

   • $56 = 15\cdot 3 + 11$
   • $15 = 11\cdot 1 + 4$
   • $11 = 4\cdot 2 + 3$
   • $4 = 3\cdot 1 + 1$
   • $3 = 1\cdot 3 + 0$
   • Last nonzero remainder: $1$
   • Answer: $\gcd(56, 15) = 1$.
4. Compute $\gcd(144, 60)$.

   Solution

   $\gcd(144, 60)$

   • $144 = 60\cdot 2 + 24$
   • $60 = 24\cdot 2 + 12$
   • $24 = 12\cdot 2 + 0$
   • Last nonzero remainder: $12$
   • Answer: $\gcd(144, 60) = 12$.
5. Compute $\gcd(101, 23)$.

   Solution

   $\gcd(101, 23)$

   • $101 = 23\cdot 4 + 9$
   • $23 = 9\cdot 2 + 5$
   • $9 = 5\cdot 1 + 4$
   • $5 = 4\cdot 1 + 1$
   • $4 = 1\cdot 4 + 0$
   • Last nonzero remainder: $1$
   • Answer: $\gcd(101, 23) = 1$.
6. Compute $\gcd(270, 192)$.

   Solution

   $\gcd(270, 192)$

   • $270 = 192\cdot 1 + 78$
   • $192 = 78\cdot 2 + 36$
   • $78 = 36\cdot 2 + 6$
   • $36 = 6\cdot 6 + 0$
   • Last nonzero remainder: $6$
   • Answer: $\gcd(270, 192) = 6$.
7. Compute $\gcd(1{,}001, 143)$.

   Solution

   $\gcd(1{,}001, 143)$

   • $1{,}001 = 143\cdot 7 + 0$
   • Last nonzero remainder: $143$
   • Answer: $\gcd(1{,}001, 143) = 143$.
8. Compute $\gcd(48, 7)$.

   Solution

   $\gcd(48, 7)$

   • $48 = 7\cdot 6 + 6$
   • $7 = 6\cdot 1 + 1$
   • $6 = 1\cdot 6 + 0$
   • Last nonzero remainder: $1$
   • Answer: $\gcd(48, 7) = 1$.
9. Compute $\gcd(-72, 30)$ (remember to use absolute values).

   Solution

   $\gcd(-72, 30)$

   • First use absolute values: $\gcd(-72, 30) = \gcd(72, 30)$.
   • $72 = 30\cdot 2 + 12$
   • $30 = 12\cdot 2 + 6$
   • $12 = 6\cdot 2 + 0$
   • Last nonzero remainder: $6$
   • Answer: $\gcd(-72, 30) = 6$.
10. True or false: If $a$ divides $b$, then $\gcd(a, b) = a$.

    Solution

    True or false: If $a$ divides $b$, then $\gcd(a, b) = a$

    • If $a$ divides $b$, then $b = ak$ for some integer $k$.
    • Any common divisor of $a$ and $b$ must divide $a$ (because $a$ already divides $b$).
    • So the largest common divisor is $a$ itself.
    • Answer: True.